Compiler CH6 Bottom-Up Parsing

Overview

• bottom-up parser
  • started from parser tree’s leaves, move to its root
  • traces a rightmost derivation in reverse
  • replace rule’s RHS with its LHS
• top-down parser
  • started from parser tree’s root toward its leave
  • trace a leftmost derivation
  • replace rule’s LHS with its RHS

Ex.

LR parsing

• 由左至右處理輸入字串
• 並以最右邊優先衍生的推導順序
  

名詞解釋

• Bottom-up
  • 因為parser從terminal symbol開始工作直到grammar’s goal symbol
• shift-reduc
  • shift symbol onto the parse stack
  • reduce 留在stack頂端的那些符號組成的字串 變成grammar’s non-terminal
• LR(k)
  • 如上

handle Pruning

informally, a substring

• matches the body of production
• whose reduction repre. 1 step along the reverse of a rightmost derivation

Ex.

formally

• 用production來作為handle，簡化表示
• 如果grammar unambiguous，所有的right-sentential form 都只有一個handle
  

handle pruning

Shift-Reduce Parsing

4 action

• shift: 將下一個input symbol移至stack top
• reduce: 從stack頂端向下，相當於將字串由右而左的縮減回nonterminal
• accept: 表示是否成功
• error: 發現syntax error 並呼叫error recovery routine

stack imple.

ex.

ex2.

LR(0) table construction

shift

• 對每個production，用dot標示辨識到的字串
• 找出closure
  • 如果production的第一個symbol是nonterminal
  • 把這個nonterminal的production也加入closure
    
• 名詞定義
  • kernal items
  • nonkernal items
  • 
• GOTO
  • 去找item，把dot往X方向移動
  • 決定有限狀態機轉換的模式
    

Ex.

1. 對一個狀態，找出closure
2. dot向右移動，定義下一個狀態
   • 可以reduce的狀態，用雙框框刮起來(就是dot在做右邊)
     
3. 得到shift的table
   

CFSM

• 最右優先匹配

completing LR(0)

state 2, 4, 6 reduced

• 因為是LR(0)就不用看下一個狀態，直接reduce
  

Ex.

• pop出多少個symbol，就要回退多少狀態
  • 其實就是看reduced的production有多少個symbol
• 龍書
  • accept在action，要看狀態和$
• 綠書
  • accept在goto
• symbol其實可以用state來代替
  • 所以可以省略
    
    

conflict

存在同時shift和reduce的情況
有兩個東西可以同時reduce

if grammar ambiguous

• 編譯器沒辦法處理
  if compiler的問題
• lookahead

ambiguous grammar

• state 5

  • reduction like left-associateve
  • shift like right-associative
    
    

• 可以reduced到兩個東西

  • 5, 7
  • 讓scanner處理
    

• 有兩個走向

  • Exprs -> E a | F b
  • 需要看最後一個symbol是甚麼
    • a or b

SLR(k) table construction

避免先加減後乘除

• 如果是LR(0)，遇到符合的直接reduced，但下一個是times優先權應該比較高
  
• SLR(k)
  

檢查symbol有沒有對應到production左式的follow set

• 再reduced
  

LALR(k) table construction

看item走的路徑決定follow

可以由LR(0), LR(1)建構出來

• LR(0)比較好做
  • 用一個圖記錄狀態轉移的過程，如上

Propagation Graph

點是一個item

• 建構出所有vertex，follow為空
  • 
• 起始production的follow，放$
• 建出所有的邊，根據LR(0)
  • 只看目前狀態內的follow
    • 
  • 就根據follow的規則走
  • 如果可以推導到empty 就加一個邊
    • 

Ex.